#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
int maxSum(vector<int> array) {
  if (array.size() == 0) {
    return 0;
  }
  else if (array.size() == 1) {
    return array[0];
  }
  vector<int> result = array;
  result[1] = max(result[0], array[1]);
  for (int i = 2; i < result.size(); ++i) {
    result[i] = max(result[i - 1], array[i] + result[i - 2]);
  }
  return *result.rbegin();
}


int maxSumRecursiveHelper(vector<int> array, int n) {
  if (n == 0) {
    return array[0];
  }
  if (n == 1) {
    return max(array[0], array[1]);
  }
  return max(maxSumRecursiveHelper(array, n - 1), array[n] + maxSumRecursiveHelper(array, n - 2));
}

int maxSumRecursive(vector<int> array) {
  return maxSumRecursiveHelper(array, array.size() - 1);
}

int main(int argc, char const *argv[]) {
  vector<int> array {75, 105, 120, 75, 90, 135} ;
  cout << maxSum(array) << endl;
  cout << maxSumRecursive(array) << endl;
  return 0;
}
